The quality of code produced by compilers has been an issue ever since the first compiler was produced. One of the principal objectives of IBM's FORTRAN I compiler, the first commercially available compiler, was to produce object code in the field of scientific computations which was comparable in code quality to that produced directly by assembly language programmers coding "by hand."
Today, higher level languages are designed to be used in every field in which computers are applicable. Even the original FORTRAN language has been bolstered to make it applicable to a wide range of programming tasks. However, it is still important that the quality of code produced by the compiler be high, especially if the resultant code is to be used in a production environment. Code produced by a skilled assembly language programmer is still the yardstick against which compiler produced code is measured.
A large number of optimization techniques have been developed and refined since the 1950's to improve the quality of compiler generated code. Indeed, many of these optimizations were known in principle, and used in some fashion by the team that produced the first FORTRAN compiler.
Optimizations that are frequently employed in optimizing compilers can be divided into two classes, which are commonly known as "global" and "peephole" optimizations. Global optimizations are those that are based on an analysis of the entire program being compiled. Examples are "code motion" (moving code out of loops) and "common subexpression elimination." Peephole optimizations are those that are based on an analysis of a relatively small region of the program, such as a "basic block," or perhaps only two adjacent instructions.
The present invention can be implemented as a global optimization, or at the basic block level, or it can use partial global information that is normally readily available from global analysis, and then refine this information at the basic block level. With more information available, it is more effective. The information from global analysis that it can profitably use is that of live/dead information. This information tells, for each register operand of an instruction, whether or not that register can be used again before it is reloaded with a new quantity.
If a register operand of an instruction is "dead," that means that the instruction is the "last use" of the register, and after executing the instruction the contents of the register could be altered in any way without affecting the execution of the program. If a register operand of an instruction is "live," on the other hand, that means that the contents of the register cannot be altered after execution of the instruction, because there may be an execution path in which the register's contents are used again.
The following references discuss live variable analysis:
J. D. Ullman, A Survey of Data Flow Analysis Techniques, Second USA-Japan Computer Conference Proceedings, AFIPS Press, Montvale, N.J., (1975), pp 335-342 (contains 37 references). PA0 A. V. Aho and J. D. Ullman, Principles of Compiler Design, Addison-Wesley, (1977). PA0 M. S. Hecht, Flow Analysis of Computer Programs, Elsevier North-Holland, N.Y., (1977).
The Motorola MC68000 is an example of a type of computer to which this invention is applicable. This computer has three forms of "add," and three forms of "add immediate," as illustrated below.
______________________________________ ADD.L r1,r2 ADDI.L #123,r1 ADD.W r1,r2 ADDI.W #123,r1 ADD.B r1,r2 ADDI.B #123,r1 ______________________________________
ADD.L (add long) adds the entire 32-bit contents of register r1 to register r2, and places the result in r2. ADD.W (add word) adds the rightmost 16 bits of r1 to the rightmost 16 bits of r2, leaving the leftmost 16 bits of r2 unchanged. ADD.B (add byte) adds the rightmost eight bits of r1 to the rightmost eight bits of r2, leaving the leftmost 24 bits of r2 unchanged. Similarly, ADDI.L (add immediate long) adds a number (123 is shown) to the entire 32-bit contents of register r1, ADDI.W adds to the rightmost 16 bits, and ADDI.B adds to the rightmost eight bits.
The instructions ADD.W and ADD.B execute faster than ADD.L, and hence are preferred in a situation in which either would do. The instructions ADDI.W and ADDI.B execute faster and occupy less storage than ADDI.L, and hence are preferred to ADDI.L.
The Motorola MC68000 has many other instruction types that exist in "long" and "short" forms, with the shorter form being faster in execution and often occupying less storage. Further details, including instruction timings, may be found in:
MC68000 16-bit Microprocessor User's Manual, Second edition, Motorola, Inc., (January 1980).
As an example of the code improvement accomplished by this invention, suppose a compiler has generated the instruction sequence:
______________________________________ ADD.L r2,r1 SUBI.L #16,r1 MOVE.W r1,6(r5) ______________________________________
and suppose further that the MOVE.W instruction, which stores the rightmost 16 bits of register r1 into storage at a location addressed by the contents of register r5 plus 6, is the last use of register r1. Then this invention will replace the ADD.L instruction with ADD.W, and the SUBI.L instruction with SUBI.W. The latter forms execute faster than the former, and the SUBI.W instruction occupies less storage than SUBI.L.